package bm10;

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * @date 2023/7/20 23:55
 * BM10.两个链表的第一个公共节点
 * https://www.nowcoder.com/practice/6ab1d9a29e88450685099d45c9e31e46?tpId=295&tqId=23257&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj
 */
public class Solution {

    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        // 边界处理
        if (pHead1 == null || pHead2 == null) {
            return null;
        }
        // 辅助指针
        ListNode curA = pHead1;
        ListNode curB = pHead2;
        // 寻找第一个公共节点, 只需要让 curA 和 curB 走的步长相等相遇即可
        while (curA != curB) {
            curA = curA == null ? pHead2 : curA.next;
            curB = curB == null ? pHead1 : curB.next;
        }
        return curA;
    }

    private static class ListNode {
        int val;
        ListNode next = null;
        public ListNode(int val) {
            this.val = val;
        }
    }
}
